package com.review.backpack_01;

import java.util.Arrays;

public class BP07_2 {
    //7. 背包问题求方案数
    //最优解的数量
    //在01背包里加入判断

    public static int knapsackProblem(int[] c, int[] v, int V) {
        int[] dp = new int[V + 1];
        int[] count = new int[V + 1];

        // 初始化，此时的count代表i=0，即没有物品可以选择时
        // 什么都不选，也是一种方案
        Arrays.fill(count, 1);

        for (int i = 0; i < c.length; i++) {
            for (int j = V; j >= c[i]; j--) {
                if (dp[j] < dp[j - c[i]] + v[i]) {
                    // 选择当前物品的收益要高，因此这里dp的选择必然是选择当前物品，
                    // 因为是必然，所以这样的方案数量不变
                    count[j] = count[j - c[i]];
                } else if (dp[j] == dp[j - c[i]] + v[i]) {
                    // 二者的收益相等，这里可以选，也可以不选
                    // 因此这里是加上count[j-v[i]]
                    count[j] += count[j - c[i]];
                } else {
                    // 不选的收益更高，那么这里dp的选择必然是不选
                    // 因此保持count[n-1][j]即可
                }
                dp[j] = Math.max(dp[j], dp[j - c[i]] + v[i]);
            }
        }
        return count[V];
    }

    public static int knapsackProblem_2(int[] c, int[] v, int V) {
        int[][] dp = new int[c.length + 1][V + 1];
        int[][] count = new int[c.length + 1][V + 1];

        // 初始化，此时的count代表i=0，即没有物品可以选择时
        // 什么都不选，也是一种方案
        for (int[] ints : count) {
            Arrays.fill(ints, 1);
        }


        for (int i = 1; i < c.length; i++) {
            for (int j = 0; j <= V; j++) {
                if (j >= c[i]) {
                    // 背包容量大于当前物品容量
                    if (dp[i - 1][j] < dp[i - 1][j - c[i]] + v[i]) {
                        // 选择当前物品的收益更高
                        // 更新当前收益
                        dp[i][j] = dp[i - 1][j - c[i]] + v[i];
                        // 当前方案只是在之前方案的基础上加了当前的物品，因此方案数量不变
                        count[i][j] = count[i - 1][j - c[i]];

                    } else if (dp[i - 1][j] == dp[i - 1][j - c[i]] + v[i]) {
                        // 两种办法收益相等
                        // 更新当前收益
                        dp[i][j] = dp[i - 1][j];
                        // 当前方案有两种选择，一是不增加当前物品，二是增加当前物品，所以方案数量等于二者之和
                        count[i][j] = count[i - 1][j] + count[i - 1][j - c[i]];
                    } else {
                        // 选择当前物品的收益更高
                        // 更新当前收益
                        dp[i][j] = dp[i - 1][j];
                        // 当前方案不增加物品，与之前的方案等同
                        count[i][j] = count[i - 1][j];
                    }
                } else {
                    // 背包容量下雨当前物品容量
                    dp[i][j] = dp[i - 1][j];
                    count[i][j] = count[i - 1][j];
                }

            }
        }
        return count[c.length][V];
    }

    public static void main(String[] args) {
        System.out.println(knapsackProblem(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
        System.out.println(knapsackProblem_2(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}
